package SwordForOffer.Problem30;

import java.util.Arrays;

public class GetLeastNumbers {
	/*
	 *输入N个整数，找出其中最小的k个数 
	 *维护一个k个数字的最大堆
	 */
	public void getLeastNumbers(int[] array,int k)
	{
		if(array==null || k < 0 || k > array.length)
			return ;

		//根据输入数组前k个数建立最大堆
		//从k+1个数开始与根节点比较
		//大于根节点，舍去
		//小于，取代根节点，重排最大堆

		int[] kArray=Arrays.copyOfRange(array, 0, k);
		buildMaxHeapify(kArray);
		for(int i=k;i<array.length;i++)
		{
			if(array[i]<kArray[0])
			{
				kArray[0]=array[i];
				maxHeapify(kArray, 0);
			}			
		}
		for(int i:kArray)
			System.out.println(i);
	}
	/*
	 * 保持堆的性质
	 */
	private void maxHeapify(int[] array,int i)
	{
		int left=2*i+1;
		int right=left+1;
		int largest=0;
		if(left<array.length && array[left]>array[i])
			largest=left;
		else 
			largest=i;
		if(right<array.length && array[right]>array[largest])
			largest=right;
		if(largest!=i)
		{
			int temp=array[i];
			array[i]=array[largest];
			array[largest]=temp;
			maxHeapify(array, largest);
		}
	}
	/*
	 * 建堆
	 */
	private void buildMaxHeapify(int[] array) {
		for(int i=array.length/2;i>=0;i--)
			maxHeapify(array, i);
	}

	public void myGetLeastNumbers(int[] array, int k) {
		if (array == null || k < 0 || k > array.length - 1){
			return;
		}
		int startIndex = 0;
		int endIndex = array.length - 1;
		int[] output;
		while (startIndex < endIndex){
			while (startIndex < k && array[startIndex] <= array[k]){
				startIndex++;
			}
			while (endIndex > k && array[endIndex] >= array[k]){
				endIndex--;
			}
			if (startIndex < endIndex){
				int temp = array[startIndex];
				array[startIndex] = array[endIndex];
				array[endIndex] = temp;
				startIndex = 0;
				endIndex = array.length - 1;
			}else {
				output = Arrays.copyOfRange(array,0,k);
				System.out.println(Arrays.toString(output));
			}
		}
	}
}
